A branch prediction is a prediction of what direction will be taken upon execution of a conditional branching instruction included within a sequence of code being executed by a machine. Branch prediction mechanism are generally known, and is used to improve the rate at which the code sequence can be executed.
In general, a Branch History Table (BHT) or Global History Register (GHR) is included with a Central Processing Unit (CPU) in a processor. The BHT is used for making branch predictions. Typically, the BHT is arranged so that the number N of rows (or depth) corresponds to the number of working registers in CPU 400, e.g., 32, 64, etc. Each row represents an R-bit word, where the value of R (or length of the BHT) corresponds to the number of columns in the BHT, where R is a positive integer. Typically, the GHR is a one-row array, also of length R, i.e., the GHR represents an R-bit word. The output of either the BHT or the GHR is an R-bit vector representing a local or global branching history, respectively.
In operation, when a prediction is to be made regarding the next conditional branching instruction, an R-bit branch history vector (HV) is output from either the BHT or the GHR. The prediction is based upon the R-bit history vector HV. Hence, the R-bit history vector HV can be described as a predicate to the branch prediction, i.e., as a branch-prediction predicate. All of the R-bits in the HV are used in making the prediction.
Generally, the value of R (again, representing the length of each entry in the BHT or the length of the GHR) is fixed as a part of the architecture of the processor. Some architectures, however, are arranged so that the value of R can be adaptively adjusted. Despite the adaptive adjustment, i.e., despite whatever size R takes, all of the R-bits in the HV are used in making the prediction.